package 力扣日常刷题.木22二月.第19天225;

/**
 * @author 帅小伙
 * @date 2022/2/25
 * @description
 * 归并排序的计算
 */
public class Demo151逆序对 {

    int[] nums,tmp;
    public int reversePairs(int[] nums) {
        this.nums = nums;
        tmp = new int[nums.length];
        return mergeCount(0,nums.length - 1);
    }

    private int mergeCount(int l,int r) {
        if(l >= r) return 0;
        int m = (l+r) / 2;

        int res = mergeCount(l,m) + mergeCount(m+1,r);
        int i = l,j = m+1;
        for (int k = l; k <= r; k++) {
            tmp[k] = nums[k];
        }

        for (int k = l; k <= r; k++) {
            if(i == m + 1) {
                nums[k] = tmp[j++];
            }else if(j == r + 1 || tmp[i] <= tmp[j]){
                nums[k] = tmp[i++];
            }else {
                nums[k] = tmp[j++];
                res += (m - i + 1);
            }
        }
        return res;
    }

}
